#include "graph_support/TestIGraph.h"

#include <boost/shared_ptr.hpp>

#include <memory.h>
#include <sstream>

#include "graph_support/IGraph.h"
#include "graph_support/attributes/LengthEdgeAttributes.h"
#include "graph_support/attributes/FlowEdgeAttributes.h"
#include "graph_support/impls/vector/VectorGraph.h"
#include "graph_support/impls/wrap_igraph/WrapIGraph.h"

#include "graph_support/alg/shortest_path/Dejkstra.h"
#include "graph_support/alg/flow/Dinic.h"
#include "graph_support/alg/traversal/GrTraversalBFS.h"

#include "graph_support/utils/test_my_graph/BoostTestUtils.h"
#include "graph_support/utils/CollectionsInit.h"


using namespace GRAPH_SUPPORT_NS;
using namespace GRAPH_SUPPORT_NS::impls;
using namespace GRAPH_SUPPORT_NS::impls::vector;
using namespace GRAPH_SUPPORT_NS::impls::wrap_igraph;
using namespace GRAPH_SUPPORT_NS::alg::flow;
using namespace GRAPH_SUPPORT_NS::alg::shortest_path;
using namespace GRAPH_SUPPORT_NS::utils;

typedef boost::shared_ptr< IGraph > IGraphPtr;

typedef IGraph::IEdgeAttributesPtr IEdgeAttributesPtr;

namespace
{
	typedef attributes::LengthEdgeAttributesTmpl< double > LengthAttributes;
	typedef attributes::FlowEdgeAttributesTmpl< double > FlowEdgeAttributes;
	typedef WrapIGraph< LengthAttributes > WrapLenGr;

	IGraphPtr newGraph( int vertexCount )
	{
		std::vector< int > vertices( vertexCount );
		for ( int i = 0; i < vertexCount; i++ )
		{
			vertices[i] = i;
		}
		return IGraphPtr( new VectorGraphTmpl< int, LengthAttributes >( vertices ) );
	}
}

void TestVertexCount()
{
	IGraphPtr graphPtr = newGraph( 123 );
	IGraph & gr = * graphPtr;
	BOOST_CHECK_EQUAL( 123, gr.igetVertexCount() );
}

namespace
{

IEdgeAttributesPtr mkLengthAttributes( double length )
{
	return IEdgeAttributesPtr(
			new IGraph::EdgeAttributesImpl< LengthAttributes >::CpAttributes(
					LengthAttributes( length ) ) );
}

}

//void TestIterateEdges()
//{
//	IGraphPtr graphPtr = newGraph( 10 );
//	IGraph & gr = * graphPtr;
//	int edgesCounter = 0;
//	size_t vertexCount = gr.igetVertexCount();
//	for ( size_t vid = 0; vid < vertexCount; vid++ )
//	{
//		int edgesCount = gr.igetOutEdgesCount( vid );
//		for ( int i = 0; i < edgesCount; i++ )
//		{
//			size_t destVid = gr.igetDestination( vid, i );
//			BOOST_CHECK_LT( destVid, vertexCount );
//
//			edgesCount++;
//		}
//	}
//	BOOST_CHECK_EQUAL( 0, edgesCounter );
//
//	// TODO: add this to universal
//	gr.iaddEdge( 0, 1, mkLengthAttributes(123 ) );
//	gr.iaddEdge( 1, 2, mkLengthAttributes(234 ) );
//	gr.iaddEdge( 3, 4, mkLengthAttributes(345 ) );
//	gr.iaddEdge( 1, 4, mkLengthAttributes(500 ) );
//	gr.iaddEdge( 4, 5, mkLengthAttributes(456 ) );
//
//	edgesCounter = 0;
//	for ( size_t vid = 0; vid < vertexCount; vid++ )
//	{
//		int edgesCount = gr.igetOutEdgesCount( vid );
//		for ( int i = 0; i < edgesCount; i++ )
//		{
//			size_t destVid = gr.igetDestination( vid, i );
//			BOOST_CHECK_LT( destVid, vertexCount );
//
//			IEdgeAttributesPtr attributesPtr = gr.igetEdgeAttributes( vid, i );
//			BOOST_CHECK( attributesPtr.get() != NULL );
//
//			IGraph::EdgeAttributesImpl< LengthAttributes >::IAttributes * lattrs =
//					dynamic_cast< IGraph::EdgeAttributesImpl< LengthAttributes >::IAttributes * >( attributesPtr.get() );
//			BOOST_CHECK( lattrs != NULL );
//			BOOST_CHECK_GT( lattrs->get()->getLength(), 120 );
//			BOOST_CHECK_LT( lattrs->get()->getLength(), 501 );
//			IGraph::EdgeAttributesImpl< FlowEdgeAttributes >::IAttributes * fattrs =
//					dynamic_cast< IGraph::EdgeAttributesImpl< FlowEdgeAttributes >::IAttributes * >( attributesPtr.get() );
//			BOOST_CHECK( fattrs == NULL );
//
//			edgesCounter++;
//		}
//	}
//	BOOST_CHECK_EQUAL( 5, edgesCounter );
//} // TODO: also test matrix-style edges access

void TestIteratorInteface()
{
	// TODO: common style of IEdgeAttributesPtr - names
	IGraphPtr graphPtr = newGraph( 10 );
	IGraph & gr = * graphPtr;

	gr.iaddEdge( 0, 1, mkLengthAttributes( 1 ) );
	gr.iaddEdge( 3, 4, mkLengthAttributes( 1 ) );
	gr.iaddEdge( 3, 5, mkLengthAttributes( 1 ) );
	gr.iaddEdge( 3, 6, mkLengthAttributes( 1 ) );

	{
	std::stringstream buf;
	size_t vid = 0;
	for ( IGraph::IEdgeIteratorPtr iptr = gr.igetOutEdgesIterator( vid ); iptr->notFinished(); iptr->next() )
	{
		size_t destVid = iptr->getDestination();
		IEdgeAttributesPtr attributes = iptr->getEdgeAttributes();
		IGraph::EdgeAttributesImpl< LengthAttributes >::IAttributes * attributesWrapPtr = dynamic_cast< IGraph::EdgeAttributesImpl< LengthAttributes >::IAttributes * >( attributes.get() );
		BOOST_CHECK( attributesWrapPtr != NULL );
		buf << vid << " -> " << destVid << " [" << attributesWrapPtr->get()->getLength() << "]; ";
	}
	BOOST_CHECK_EQUAL( std::string( "0 -> 1 [1]; " ), buf.str() );
	}

	{
	std::stringstream buf;
	size_t vid = 3;
	IGraph::IEdgeIteratorPtr iptr = gr.igetOutEdgesIterator();
	IGraph::IEdgeIterator & iter = * iptr;
	for ( gr.igetOutEdgesIterator( vid, iter ); iter.notFinished(); iter.next() )
	{
		size_t destVid = iter.getDestination();
		IEdgeAttributesPtr attributes = iter.getEdgeAttributes();
		IGraph::EdgeAttributesImpl< LengthAttributes >::IAttributes * attributesWrapPtr = dynamic_cast< IGraph::EdgeAttributesImpl< LengthAttributes >::IAttributes * >( attributes.get() );
		BOOST_CHECK( attributesWrapPtr != NULL );
		buf << vid << " -> " << destVid << " [" << attributesWrapPtr->get()->getLength() << "]; ";
	}
	BOOST_CHECK_EQUAL( std::string( "3 -> 4 [1]; 3 -> 5 [1]; 3 -> 6 [1]; " ), buf.str() );
	}
} // TODO: also test matrix-style edges access

void TestIAttributesChange()
{
	IGraphPtr graphPtr = newGraph( 10 );
	IGraph & gr = * graphPtr;

	BOOST_CHECK_EQUAL( false, gr.igetOutEdgesIterator( 0 )->notFinished() );
	gr.iaddEdge( 0, 1, mkLengthAttributes( 123 ) );
	BOOST_CHECK_EQUAL( true,  gr.igetOutEdgesIterator( 0 )->notFinished() );
	IEdgeAttributesPtr attributesPtr = gr.igetOutEdgesIterator( 0 )->getEdgeAttributes();
	IGraph::EdgeAttributesImpl< LengthAttributes >::IAttributes * lattrs =
			dynamic_cast< IGraph::EdgeAttributesImpl< LengthAttributes >::IAttributes * >(
					attributesPtr.get() );
	BOOST_CHECK( lattrs != NULL );
	BOOST_CHECK_EQUAL( 123, lattrs->get()->getLength() );
	lattrs->get()->setLength( 234 );
	BOOST_CHECK_EQUAL( 234, lattrs->get()->getLength() );

	attributesPtr = gr.igetOutEdgesIterator( 0 )->getEdgeAttributes();
	lattrs =
			dynamic_cast< IGraph::EdgeAttributesImpl< LengthAttributes >::IAttributes * >(
					attributesPtr.get() );
	BOOST_CHECK( lattrs != NULL );
	BOOST_CHECK_EQUAL( 234, lattrs->get()->getLength() );
}

void TestFlowOnIGraph()
{
	typedef VectorGraphTmpl< int, FlowEdgeAttributes > GrNet;

	GrNet netGr(
			( std::vector< int > ) arr2vector< int >( ( const int [] ) { 0, 1, 2, 3 } ), true );
	{
	Dinic< GrNet > dinic( netGr );
	dinic( 0, 1 );
	BOOST_CHECK_CLOSE( 0, dinic.getTotalFlow(), 1e-5 );
	}

	IGraph * graphPtr = & netGr;
	IGraph & gr = * graphPtr;

	BOOST_CHECK_EQUAL( false, gr.igetOutEdgesIterator( 0 )->notFinished() );
	IEdgeAttributesPtr attrs( new RTTICpStorage< FlowEdgeAttributes >( FlowEdgeAttributes( 321 ) ) );
	gr.iaddEdge( 0, 1, attrs );

	IEdgeAttributesPtr attributesPtr = gr.igetOutEdgesIterator( 0 )->getEdgeAttributes();
	IGraph::EdgeAttributesImpl< FlowEdgeAttributes >::IAttributes * fattrs =
			dynamic_cast< IGraph::EdgeAttributesImpl< FlowEdgeAttributes >::IAttributes * >( attributesPtr.get() );
	BOOST_CHECK( NULL != fattrs );
	BOOST_CHECK_CLOSE( 321, fattrs->get()->getCapacity(), 1e-5 );
	{
	Dinic< GrNet > dinic( netGr );
	dinic( 0, 1 );
	BOOST_CHECK_CLOSE( 321, dinic.getTotalFlow(), 1e-5 );
	}
}

void TestWrap4IGraph()
{
	{
	IGraphPtr graphPtr = newGraph( 10 );
	IGraph & gr = * graphPtr;

	gr.iaddEdge( 0, 1, mkLengthAttributes( 100 ) );
	gr.iaddEdge( 1, 2, mkLengthAttributes( 100 ) );
	gr.iaddEdge( 2, 3, mkLengthAttributes( 100 ) );
	gr.iaddEdge( 3, 4, mkLengthAttributes( 100 ) );
	gr.iaddEdge( 4, 5, mkLengthAttributes( 100 ) );
	gr.iaddEdge( 5, 6, mkLengthAttributes( 100 ) );
	gr.iaddEdge( 6, 7, mkLengthAttributes( 100 ) );

	WrapLenGr wgr( graphPtr );
	{
	Dejkstra< WrapLenGr > dejkstra( wgr );
	dejkstra( 0 );
	BOOST_CHECK_CLOSE( 700, dejkstra.getDistance( 7 ), 1e-5 );
	}

	gr.iaddEdge( 0, 4, mkLengthAttributes( 1 ) );
	{
	Dejkstra< WrapLenGr > dejkstra( wgr );
	dejkstra( 0 );
	BOOST_CHECK_CLOSE( 301, dejkstra.getDistance( 7 ), 1e-5 );
	}

	gr.iaddEdge( 1, 6, mkLengthAttributes( 2 ) );
	{
	Dejkstra< WrapLenGr > dejkstra( wgr );
	dejkstra( 0 );
	BOOST_CHECK_CLOSE( 202, dejkstra.getDistance( 7 ), 1e-5 );
	}
	}

	{
	typedef WrapIGraph< FlowEdgeAttributes > WrapNet;

	std::vector< int > vertices = arr2vector< int >( ( const int [] ) { 0, 1, 2, 3, 4, 5 } );
	std::auto_ptr< VectorGraphTmpl< int, FlowEdgeAttributes > > vecNetPtr( new VectorGraphTmpl< int, FlowEdgeAttributes >( vertices, true ) );
	VectorGraphTmpl< int, FlowEdgeAttributes > * vecNetRPtr = vecNetPtr.get();
	IGraphPtr netPtr( vecNetPtr.release() );
	IGraph & gr = * netPtr;
	WrapNet wgr( netPtr );

	{
	Dinic< WrapNet > dinic( wgr );
	dinic( 0, 1 );
	BOOST_CHECK_CLOSE( 0, dinic.getTotalFlow(), 1e-5 );
	}

	IEdgeAttributesPtr attrs( new IGraph::EdgeAttributesImpl< FlowEdgeAttributes >::CpAttributes( FlowEdgeAttributes( 321.0 ) ) );
	gr.iaddEdge( 0, 1, attrs );
	{
	Dinic< WrapNet > dinic( wgr );
	dinic( 0, 1 );
	BOOST_CHECK_CLOSE( 321, dinic.getTotalFlow(), 1e-5 );
	}

	vecNetRPtr->addEdge( 0, 2, 32 );
	vecNetRPtr->addEdge( 2, 1, 23 );
	{
	Dinic< WrapNet > dinic( wgr );
	dinic( 0, 1 );
	BOOST_CHECK_CLOSE( 344, dinic.getTotalFlow(), 1e-5 );
	}
	}
}

namespace TestWrap4IGraph_NS
{

void foo( WrapIGraph< LengthAttributes >::GrEdgePtr edge )
{
}

}

void TestBFSOnIGraph()
{
	using namespace GRAPH_SUPPORT_NS::alg::traversal;
	using namespace TestWrap4IGraph_NS;

	IGraphPtr grPtr = newGraph( 10 );
	IGraph & gr = * grPtr;
	gr.iaddEdge( 0, 1, mkLengthAttributes( 1 ) );
	gr.iaddEdge( 0, 2, mkLengthAttributes( 1 ) );
	gr.iaddEdge( 0, 3, mkLengthAttributes( 1 ) );
	gr.iaddEdge( 1, 4, mkLengthAttributes( 1 ) );

	WrapLenGr graph( grPtr );

	GrTraversalBFSAllEdges( graph, 0, foo );
}

